{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Get Watched Videos by Your Friends"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #graph #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #图 #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: watchedVideosByFriends"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #获取你好友已观看的视频"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有&nbsp;<code>n</code> 个人，每个人都有一个&nbsp; <code>0</code>&nbsp;到&nbsp;<code>n-1</code>&nbsp;的唯一&nbsp;<em>id</em>&nbsp;。</p>\n",
    "\n",
    "<p>给你数组 <code>watchedVideos</code>&nbsp; 和&nbsp;<code>friends</code>&nbsp;，其中&nbsp;<code>watchedVideos[i]</code>&nbsp; 和&nbsp;<code>friends[i]</code>&nbsp;分别表示&nbsp;<code>id = i</code>&nbsp;的人观看过的视频列表和他的好友列表。</p>\n",
    "\n",
    "<p>Level&nbsp;<strong>1</strong>&nbsp;的视频包含所有你好友观看过的视频，level&nbsp;<strong>2</strong>&nbsp;的视频包含所有你好友的好友观看过的视频，以此类推。一般的，Level 为 <strong>k</strong>&nbsp;的视频包含所有从你出发，最短距离为&nbsp;<strong>k</strong>&nbsp;的好友观看过的视频。</p>\n",
    "\n",
    "<p>给定你的&nbsp;<code>id</code>&nbsp; 和一个&nbsp;<code>level</code>&nbsp;值，请你找出所有指定 <code>level</code> 的视频，并将它们按观看频率升序返回。如果有频率相同的视频，请将它们按字母顺序从小到大排列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/03/leetcode_friends_1.png\" style=\"height: 179px; width: 129px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>watchedVideos = [[&quot;A&quot;,&quot;B&quot;],[&quot;C&quot;],[&quot;B&quot;,&quot;C&quot;],[&quot;D&quot;]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1\n",
    "<strong>输出：</strong>[&quot;B&quot;,&quot;C&quot;] \n",
    "<strong>解释：</strong>\n",
    "你的 id 为 0（绿色），你的朋友包括（黄色）：\n",
    "id 为 1 -&gt; watchedVideos = [&quot;C&quot;]&nbsp;\n",
    "id 为 2 -&gt; watchedVideos = [&quot;B&quot;,&quot;C&quot;]&nbsp;\n",
    "你朋友观看过视频的频率为：\n",
    "B -&gt; 1&nbsp;\n",
    "C -&gt; 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/03/leetcode_friends_2.png\" style=\"height: 179px; width: 129px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>watchedVideos = [[&quot;A&quot;,&quot;B&quot;],[&quot;C&quot;],[&quot;B&quot;,&quot;C&quot;],[&quot;D&quot;]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2\n",
    "<strong>输出：</strong>[&quot;D&quot;]\n",
    "<strong>解释：</strong>\n",
    "你的 id 为 0（绿色），你朋友的朋友只有一个人，他的 id 为 3（黄色）。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == watchedVideos.length ==&nbsp;friends.length</code></li>\n",
    "\t<li><code>2 &lt;= n&nbsp;&lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;watchedVideos[i].length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;watchedVideos[i][j].length &lt;= 8</code></li>\n",
    "\t<li><code>0 &lt;= friends[i].length &lt; n</code></li>\n",
    "\t<li><code>0 &lt;= friends[i][j]&nbsp;&lt; n</code></li>\n",
    "\t<li><code>0 &lt;= id &lt; n</code></li>\n",
    "\t<li><code>1 &lt;= level &lt; n</code></li>\n",
    "\t<li>如果&nbsp;<code>friends[i]</code> 包含&nbsp;<code>j</code>&nbsp;，那么&nbsp;<code>friends[j]</code> 包含&nbsp;<code>i</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [get-watched-videos-by-your-friends](https://leetcode.cn/problems/get-watched-videos-by-your-friends/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [get-watched-videos-by-your-friends](https://leetcode.cn/problems/get-watched-videos-by-your-friends/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"A\",\"B\"],[\"C\"],[\"B\",\"C\"],[\"D\"]]\\n[[1,2],[0,3],[0,3],[1,2]]\\n0\\n1', '[[\"A\",\"B\"],[\"C\"],[\"B\",\"C\"],[\"D\"]]\\n[[1,2],[0,3],[0,3],[1,2]]\\n0\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id_: int, level: int) -> List[str]:\n",
    "        # BFS\n",
    "        q = {id_}\n",
    "        for _ in range(level):\n",
    "            tmp = q\n",
    "            q = set()   # set去重或许会快？\n",
    "            for id_ in tmp:\n",
    "                if friends[id_]:\n",
    "                    q.update(friends[id_])\n",
    "                    friends[id_] = False\n",
    "        \n",
    "        # 获取朋友看过的所有视频\n",
    "        # 记录视频的观看数\n",
    "        c = Counter()\n",
    "        for id_ in q:\n",
    "            if friends[id_]:\n",
    "                c.update(watchedVideos[id_])\n",
    "        return sorted(c, key=lambda k:(c[k], k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        queue = [id]\n",
    "        seen = set()\n",
    "        seen.add(id)\n",
    "        for _ in range(level):\n",
    "            for _ in range(len(queue)):\n",
    "                vertex = queue.pop(0)\n",
    "                nodes = friends[vertex]\n",
    "                for node in nodes:\n",
    "                    if node not in seen:\n",
    "                        queue.append(node)\n",
    "                        seen.add(node)\n",
    "        watch = {}\n",
    "        for i in queue:\n",
    "            for w in watchedVideos[i]:\n",
    "                if w not in watch:\n",
    "                    watch[w] = 1\n",
    "                else:\n",
    "                    watch[w] += 1\n",
    "        res = sorted(watch, key=lambda x:(watch[x], x))\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n=len(friends)\n",
    "        judge=[1 for i in range(n)]\n",
    "        judge[id]=0\n",
    "        ans=[]\n",
    "        ss=[id]\n",
    "        while level>0:\n",
    "            level-=1\n",
    "            k=[]\n",
    "            for t in ss:\n",
    "                for i in friends[t]:\n",
    "                    if judge[i]:\n",
    "                        k.append(i)\n",
    "                        judge[i]=0\n",
    "            ss=k\n",
    "        apa={1:[]}\n",
    "        je={}\n",
    "        p=[]\n",
    "        for i in range(len(ss)):\n",
    "                for j in watchedVideos[ss[i]]:\n",
    "                    \n",
    "                    if j not in p:\n",
    "                        apa[1].append(j)\n",
    "                        p.append(j)\n",
    "                        je[j]=1\n",
    "                    else:\n",
    "                        apa[je[j]].remove(j)\n",
    "                        je[j]+=1\n",
    "                        if je[j] in apa:\n",
    "                            apa[je[j]].append(j)\n",
    "                        else:\n",
    "                            apa[je[j]]=[j]\n",
    "        st=list(apa.keys())\n",
    "        sss=[]\n",
    "        for i in range (len(st)):\n",
    "            apa[st[i]].sort()\n",
    "            sss=sss+apa[st[i]]\n",
    "        return sss\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n=len(friends)\n",
    "        judge=[1 for i in range(n)]\n",
    "        judge[id]=0\n",
    "        ans=[]\n",
    "        ss=[id]\n",
    "        while level>0:\n",
    "            level-=1\n",
    "            k=[]\n",
    "            for t in ss:\n",
    "                for i in friends[t]:\n",
    "                    if judge[i]:\n",
    "                        k.append(i)\n",
    "                        judge[i]=0\n",
    "            ss=k\n",
    "        apa={1:[]}\n",
    "        je={}\n",
    "        p=[]\n",
    "        for i in range(len(ss)):\n",
    "                for j in watchedVideos[ss[i]]:\n",
    "                    \n",
    "                    if j not in p:\n",
    "                        apa[1].append(j)\n",
    "                        p.append(j)\n",
    "                        je[j]=1\n",
    "                    else:\n",
    "                        apa[je[j]].remove(j)\n",
    "                        je[j]+=1\n",
    "                        if je[j] in apa:\n",
    "                            apa[je[j]].append(j)\n",
    "                        else:\n",
    "                            apa[je[j]]=[j]\n",
    "        st=list(apa.keys())\n",
    "        sss=[]\n",
    "        for i in range (len(st)):\n",
    "            apa[st[i]].sort()\n",
    "            sss=sss+apa[st[i]]\n",
    "        return sss\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id_: int, level: int) -> List[str]:\n",
    "        # BFS\n",
    "        q = {id_}\n",
    "        for _ in range(level):\n",
    "            tmp = q\n",
    "            q = set()   # set去重或许会快？\n",
    "            for id_ in tmp:\n",
    "                if friends[id_]:\n",
    "                    q.update(friends[id_])\n",
    "                friends[id_] = False\n",
    "        \n",
    "        # 获取朋友看过的所有视频\n",
    "        # 记录视频的观看数\n",
    "        c = Counter()\n",
    "        for id_ in q:\n",
    "            if friends[id_]:\n",
    "                c.update(watchedVideos[id_])\n",
    "        return sorted(c, key=lambda k:(c[k], k))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], _id: int, level: int) -> List[str]:\n",
    "        n, dq = len(watchedVideos), deque()\n",
    "        levels = [-1] * n\n",
    "        dq.append(_id)\n",
    "        levels[_id] = 0\n",
    "        while dq and levels[dq[0]] < level:\n",
    "            i = dq.popleft()\n",
    "            l = levels[i]\n",
    "            for f in friends[i]:\n",
    "                if levels[f] == -1:\n",
    "                    dq.append(f)\n",
    "                    levels[f] = l + 1\n",
    "        cnt = {}\n",
    "        for i in dq:\n",
    "            for v in watchedVideos[i]:\n",
    "                cnt[v] = cnt.get(v, 0) + 1\n",
    "        return sorted(list(cnt.keys()), key=lambda x: (cnt.get(x), x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        # 1. O(N^2) build adjacency list of undirected graph\n",
    "        n = len(watchedVideos)\n",
    "        \n",
    "        # 2. BFS start from vertex id, go `level` depth\n",
    "        videos = []\n",
    "        queue = deque([id])\n",
    "        visited = [False] * n \n",
    "        visited[id] = True \n",
    "\n",
    "        while queue and level > 0:\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                for neighbor in friends[node]:\n",
    "                    if not visited[neighbor]:\n",
    "                        queue.append(neighbor)\n",
    "                        visited[neighbor] = True \n",
    "            level -= 1\n",
    "\n",
    "        # 3. order videos by frequency and name\n",
    "        videos = [watchedVideos[i] for i in queue]\n",
    "        freq = Counter(itertools.chain(*videos))\n",
    "        ans = sorted(freq.keys(), key=lambda x: (freq[x], x))\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        # 获取给定id的朋友们\n",
    "        def getFriendIds(friends, ids):\n",
    "            rets = []\n",
    "            for id in ids:\n",
    "                rets.extend(friends[id])\n",
    "\n",
    "            return list(set(rets) - set(ids))\n",
    "\n",
    "        # 初始id\n",
    "        startids = [[id]]\n",
    "\n",
    "        # 获取第level层id\n",
    "        for i in range(level):\n",
    "            startids.append(getFriendIds(friends, startids[i]))\n",
    "\n",
    "        # 要去掉朋友中的自己\n",
    "        if level > 1:\n",
    "            startids[level] = list(set(startids[level]) - set(startids[level-2]))\n",
    "        \n",
    "        # 获取id对应的视频\n",
    "        videos = []\n",
    "        for id in startids[level]:\n",
    "            videos.extend(watchedVideos[id])\n",
    "\n",
    "        # 排序\n",
    "        videos.sort()\n",
    "        vd = Counter(videos)\n",
    "        sortedVideo = sorted(vd.items(), key=lambda x: x[1])\n",
    "        return [d[0] for d in sortedVideo]   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        now = 0        # 当前层数\n",
    "        flag = set()   # 已经访问过的好友\n",
    "        fre = set([id])# 第 now 层朋友圈\n",
    "        videos = []\n",
    "        '''\n",
    "        1. 构建第 now 层列表\n",
    "        '''\n",
    "        while now < level:\n",
    "            tmp = set()\n",
    "            for i in fre:\n",
    "                if i in flag: # 已经访问过的好友不算\n",
    "                    continue\n",
    "                flag.add(i)\n",
    "                tmp.update(friends[i])\n",
    "            fre = tmp\n",
    "            now += 1\n",
    "        fre = [x for x in fre if x not in flag] # 去除已经访问过的\n",
    "        '''\n",
    "        2. 统计好友影片数\n",
    "        '''\n",
    "        for f in fre:\n",
    "            for v in watchedVideos[f]:\n",
    "                videos.append(v)\n",
    "        result = collections.defaultdict(int)\n",
    "        for v in videos:\n",
    "            result[v] += 1\n",
    "        #---- 排序\n",
    "        res = list( result.keys() )\n",
    "        res.sort(key = lambda v : (result[v], v))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        q = deque()\n",
    "        visit = {id, }\n",
    "        q.append(id)\n",
    "        cnt = Counter()\n",
    "        while q:\n",
    "            if level == 0:\n",
    "                for i in q:\n",
    "                    for v in watchedVideos[i]:\n",
    "                        cnt[v] += 1\n",
    "                return sorted(cnt.keys(), key=lambda k:(cnt[k], k))\n",
    "            else:\n",
    "                n = len(q)\n",
    "                level -= 1\n",
    "                for i in range(n):\n",
    "                    p = q.popleft()\n",
    "                    for f in friends[p]:\n",
    "                        if f not in visit:\n",
    "                            q.append(f)\n",
    "                            visit.add(f)\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        # 1. O(N^2) build adjacency list of undirected graph\n",
    "        n = len(watchedVideos)\n",
    "        \n",
    "        # 2. BFS start from vertex id, go `level` depth\n",
    "        videos = []\n",
    "        queue = deque([id])\n",
    "        visited = [False] * n \n",
    "        visited[id] = True \n",
    "\n",
    "        for _ in range(level):\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                for neighbor in friends[node]:\n",
    "                    if not visited[neighbor]:\n",
    "                        queue.append(neighbor)\n",
    "                        visited[neighbor] = True \n",
    "\n",
    "        # 3. order videos by frequency and name\n",
    "        videos = [watchedVideos[i] for i in queue]\n",
    "        freq = Counter(itertools.chain(*videos))\n",
    "        ans = sorted(freq.keys(), key=lambda x: (freq[x], x))\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        friendQueue = collections.deque()\n",
    "        friendQueue.append(id)\n",
    "        visited = [False] * len(friends)\n",
    "        visited[id] = True\n",
    "        step = 0\n",
    "        while step < level and friendQueue:\n",
    "            for i in range(len(friendQueue)):\n",
    "                curNode = friendQueue.popleft()\n",
    "                for friend in friends[curNode]:\n",
    "                    if not visited[friend]:\n",
    "                        friendQueue.append(friend)\n",
    "                        visited[friend] = True\n",
    "            step += 1\n",
    "        theDict = collections.defaultdict(int)\n",
    "        for friend in friendQueue:\n",
    "            for video in watchedVideos[friend]:\n",
    "                theDict[video] += 1\n",
    "        theQueue = []\n",
    "        heapq.heapify(theQueue)\n",
    "        for key, value in theDict.items():\n",
    "            heapq.heappush(theQueue, (value, key))\n",
    "        record = []\n",
    "        while theQueue:\n",
    "            record.append(heapq.heappop(theQueue)[1])\n",
    "        return record"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        vis = {id}\n",
    "        queue = deque([id])\n",
    "        for _ in range(level):\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                for j in friends[node]:\n",
    "                    if j not in vis:\n",
    "                        queue.append(j)\n",
    "                        vis.add(j)\n",
    "        arr = []\n",
    "        while queue:\n",
    "            arr += watchedVideos[queue.popleft()]\n",
    "        c = Counter(arr)\n",
    "        x = list(sorted(c, key = lambda x:(c[x], x)))\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id_: int, level: int) -> List[str]:\n",
    "        # BFS\n",
    "        q = [id_]\n",
    "        for _ in range(level):\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for id_ in tmp:\n",
    "                if friends[id_]:\n",
    "                    q.extend(friends[id_])\n",
    "                    friends[id_] = False\n",
    "        \n",
    "        # 获取朋友看过的所有视频\n",
    "        # 记录视频的观看数\n",
    "        c = Counter()\n",
    "        for id_ in q:\n",
    "            if friends[id_]:\n",
    "                friends[id_] = False\n",
    "                c.update(watchedVideos[id_])\n",
    "        return sorted(c, key=lambda k:(c[k], k))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id_: int, level: int) -> List[str]:\n",
    "        # BFS\n",
    "        q = {id_}\n",
    "        for _ in range(level):\n",
    "            tmp = q\n",
    "            q = set()   # set去重或许会快？\n",
    "            for id_ in tmp:\n",
    "                if friends[id_]:\n",
    "                    q.update(friends[id_])\n",
    "                friends[id_] = False\n",
    "        \n",
    "        # 获取朋友看过的所有视频\n",
    "        # 记录视频的观看数\n",
    "        c = Counter()\n",
    "        for id_ in q:\n",
    "            if friends[id_]:\n",
    "                c.update(watchedVideos[id_])\n",
    "        return sorted(c, key=lambda k:(c[k], k))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        queue = [id]\n",
    "        seen = set()\n",
    "        seen.add(id)\n",
    "        for _ in range(level):\n",
    "            tmp = []\n",
    "            for vertex in queue:\n",
    "                nodes = friends[vertex]\n",
    "                for node in nodes:\n",
    "                    if node not in seen:\n",
    "                        tmp.append(node)\n",
    "                        seen.add(node)\n",
    "            queue = tmp\n",
    "        watch = []\n",
    "        for i in queue:\n",
    "            watch.extend(watchedVideos[i])\n",
    "        watch = dict(Counter(watch))\n",
    "        res = sorted(watch, key=lambda x:(watch[x], x))\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        queue = [id]\n",
    "        seen = set()\n",
    "        seen.add(id)\n",
    "        for _ in range(level):\n",
    "            tmp = []\n",
    "            for vertex in queue:\n",
    "                nodes = friends[vertex]\n",
    "                for node in nodes:\n",
    "                    if node not in seen:\n",
    "                        tmp.append(node)\n",
    "                        seen.add(node)\n",
    "            queue = tmp\n",
    "        watch = {}\n",
    "        for i in queue:\n",
    "            for w in watchedVideos[i]:\n",
    "                if w not in watch:\n",
    "                    watch[w] = 1\n",
    "                else:\n",
    "                    watch[w] += 1\n",
    "        res = sorted(watch, key=lambda x:(watch[x], x))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> \\\n",
    "    List[str]:\n",
    "        n = len(watchedVideos)\n",
    "        cnt = defaultdict(int)\n",
    "        q = deque([id])\n",
    "        cur_level = 0\n",
    "        visit = [False] * n\n",
    "        visit[id] = True\n",
    "        while q:\n",
    "            if cur_level == level:\n",
    "                break\n",
    "            t = deque()\n",
    "            while q:\n",
    "                front = q.popleft()\n",
    "                for v in friends[front]:\n",
    "                    if visit[v]:\n",
    "                        continue\n",
    "                    visit[v] = True\n",
    "                    t.append(v)\n",
    "            q = t\n",
    "            cur_level += 1\n",
    "        while q:\n",
    "            front = q.popleft()\n",
    "            for video in watchedVideos[front]:\n",
    "                cnt[video] += 1\n",
    "        return sorted(list(cnt.keys()), key=lambda k: (cnt[k], k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        C, R = set(), {id}\n",
    "        for i in range(level):\n",
    "            C |= R\n",
    "            R = set(sum([friends[r] for r in R], [])) - C\n",
    "        D = collections.Counter(sum([watchedVideos[r] for r in R], []))\n",
    "        return sorted(D, key = lambda a: (D[a], a))\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        q=deque([id])\n",
    "        seen=set([id])\n",
    "        while level:\n",
    "            size=len(q)\n",
    "            for _ in range(size):\n",
    "                user=q.popleft()\n",
    "                for friend in friends[user]:\n",
    "                    if friend not in seen:\n",
    "                        q.append(friend)\n",
    "                        seen.add(friend)\n",
    "            level-=1\n",
    "     \n",
    "        c=Counter(reduce(lambda x,y:x+y,[watchedVideos[i] for i in q]))\n",
    "  \n",
    "        return sorted(c.keys(),key=lambda x:(c[x],x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        # 获取给定id的朋友们\n",
    "        def getFriendIds(friends, ids):\n",
    "            rets = []\n",
    "            for id in ids:\n",
    "                rets.extend(friends[id])\n",
    "            print(ids, rets)\n",
    "            return list(set(rets) - set(ids))\n",
    "\n",
    "        # 初始id\n",
    "        startids = [[id]]\n",
    "\n",
    "        # 获取第level层id\n",
    "        for i in range(level):\n",
    "            startids.append(getFriendIds(friends, startids[i]))\n",
    "\n",
    "        # 要去掉朋友中的自己\n",
    "        if level > 1:\n",
    "            startids[level] = list(set(startids[level]) - set(startids[level-2]))\n",
    "        \n",
    "        # 获取id对应的视频\n",
    "        videos = []\n",
    "        for id in startids[level]:\n",
    "            videos.extend(watchedVideos[id])\n",
    "\n",
    "        # 排序\n",
    "        videos.sort()\n",
    "        vd = Counter(videos)\n",
    "        sortedVideo = sorted(vd.items(), key=lambda x: x[1])\n",
    "        return [d[0] for d in sortedVideo]   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        \n",
    "        n = len(watchedVideos)\n",
    "        visit = [-1]*n\n",
    "        stack = [id]\n",
    "        visit[id] = 0\n",
    "        while stack:\n",
    "            nex=  []\n",
    "            for i in stack:\n",
    "                for j in friends[i]:\n",
    "                    if visit[j] == -1:\n",
    "                        visit[j] = visit[i]+1\n",
    "                        nex.append(j)\n",
    "            stack = nex[:]\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if visit[i] == level:\n",
    "                ans.extend(watchedVideos[i])\n",
    "        cnt = Counter(ans)\n",
    "        res = [[cnt[k], k] for k in cnt]\n",
    "        res.sort()\n",
    "        return [ls[1] for ls in res]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        f = set([id])\n",
    "        seen = set()\n",
    "\n",
    "        while level > 0:\n",
    "            new_f = set()\n",
    "\n",
    "            for j in f:\n",
    "                for i in friends[j]:\n",
    "                    if i != id and i not in seen:\n",
    "                        new_f.add(i)\n",
    "                        seen.add(i)\n",
    "\n",
    "            f = new_f\n",
    "            level -= 1\n",
    "\n",
    "        record = {}\n",
    "\n",
    "        for i in f:\n",
    "            for m in watchedVideos[i]:\n",
    "                record.setdefault(m, 0)\n",
    "                record[m] += 1\n",
    "\n",
    "        return list(map(lambda x: x[0], sorted(record.items(), key = lambda x: f\"{x[1]:010d}\" + x[0])))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        q = deque([id])\n",
    "        vis = [False] * len(watchedVideos)\n",
    "        vis[id] = True\n",
    "        for _ in range(level):\n",
    "            for _ in range(len(q)):\n",
    "                x = q.popleft()\n",
    "                for y in friends[x]:\n",
    "                    if not vis[y]:\n",
    "                        q.append(y)\n",
    "                        vis[y] = True\n",
    "        v = []\n",
    "        for x in q:\n",
    "            v.extend(watchedVideos[x])\n",
    "        c = Counter(v)\n",
    "        return sorted([k for k in c], key=lambda x:(c[x], x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "    mk = [0] * len(friends)\n",
    "    q = deque([(id, 0)])\n",
    "    mk[id] = 1\n",
    "    m = {}\n",
    "    while len(q) > 0:\n",
    "      i, l = q.popleft()\n",
    "      nl = l + 1\n",
    "      if l == level:\n",
    "        # print(f\"fri  {i} => {watchedVideos[i]}\")\n",
    "        for w in watchedVideos[i]:\n",
    "          c = m.get(w, 0) + 1\n",
    "          m[w] = c\n",
    "      else:\n",
    "        for f in friends[i]:\n",
    "          if 0 == mk[f]:\n",
    "            mk[f] = 1\n",
    "            q.append((f, nl))\n",
    "    dat = []\n",
    "    for k, v in m.items():\n",
    "      dat.append((v, k))\n",
    "    dat.sort()\n",
    "    ret = []\n",
    "    for _, n in dat:\n",
    "      ret.append(n)\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "        used = [False] * n\n",
    "        q = collections.deque([id])\n",
    "        used[id] = True\n",
    "        for _ in range(level):\n",
    "            span = len(q)\n",
    "            for i in range(span):\n",
    "                u = q.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if not used[v]:\n",
    "                        q.append(v)\n",
    "                        used[v] = True\n",
    "        \n",
    "        freq = collections.Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.pop()\n",
    "            for watched in watchedVideos[u]:\n",
    "                freq[watched] += 1\n",
    "\n",
    "        videos = list(freq.items())\n",
    "        videos.sort(key=lambda x: (x[1], x[0]))\n",
    "\n",
    "        ans = [video[0] for video in videos]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "        used = [False] * n\n",
    "        q = collections.deque([id])\n",
    "        used[id] = True\n",
    "        for _ in range(level):\n",
    "            span = len(q)\n",
    "            for i in range(span):\n",
    "                u = q.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if not used[v]:\n",
    "                        q.append(v)\n",
    "                        used[v] = True\n",
    "\n",
    "        freq = collections.Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.pop()\n",
    "            for watched in watchedVideos[u]:\n",
    "                freq[watched] += 1\n",
    "\n",
    "        videos = list(freq.items())\n",
    "        videos.sort(key=lambda x: (x[1], x[0]))\n",
    "\n",
    "        ans = [video[0] for video in videos]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "        people = deque([id])\n",
    "        used = [False]*n\n",
    "        used[id] = True\n",
    "        for _ in range(level):\n",
    "            span = len(people)\n",
    "            for i in range(span):\n",
    "                u = people.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if used[v] == False:\n",
    "                        people.append(v)\n",
    "                        used[v] = True\n",
    "        count = Counter()\n",
    "        for num in people:\n",
    "            for video in watchedVideos[num]:\n",
    "                count[video] += 1\n",
    "        count = list(count.items())\n",
    "        count.sort(key = lambda x: (x[1],x[0]))\n",
    "        ans = [x[0] for x in count]\n",
    "        return ans\n",
    "        '''\n",
    "        n = len(friends)\n",
    "        used = [False] * n\n",
    "        q = collections.deque([id])\n",
    "        used[id] = True\n",
    "        for _ in range(level):\n",
    "            span = len(q)\n",
    "            for i in range(span):\n",
    "                u = q.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if not used[v]:\n",
    "                        q.append(v)\n",
    "                        used[v] = True\n",
    "        \n",
    "        freq = collections.Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.pop()\n",
    "            for watched in watchedVideos[u]:\n",
    "                freq[watched] += 1\n",
    "\n",
    "        videos = list(freq.items())\n",
    "        print(videos)\n",
    "        videos.sort(key=lambda x: (x[1], x[0]))\n",
    "        print(videos)\n",
    "        ans = [video[0] for video in videos]\n",
    "        return ans\n",
    "        '''\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "        used = [False] * n\n",
    "        q = collections.deque([id])\n",
    "        used[id] = True\n",
    "        for _ in range(level):\n",
    "            span = len(q)\n",
    "            for i in range(span):\n",
    "                u = q.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if not used[v]:\n",
    "                        q.append(v)\n",
    "                        used[v] = True\n",
    "        freq = collections.Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.popleft()\n",
    "            for watched in watchedVideos[u]:\n",
    "                freq[watched] += 1\n",
    "        videos = list(freq.items())\n",
    "        videos.sort(key = lambda x: (x[1], x[0]))\n",
    "\n",
    "        res = [video[0] for video in videos]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        max_val = float('inf')\n",
    "        n = len(friends)\n",
    "        costs = [max_val for _ in range(n)]\n",
    "        costs[id] = 0\n",
    "        process = []\n",
    "        def find_lowest_cost_node():\n",
    "            lowest_cost = max_val\n",
    "            lowest_cost_node = None\n",
    "            for k, v in enumerate(costs):\n",
    "                if k not in process and v < lowest_cost:\n",
    "                    lowest_cost = v\n",
    "                    lowest_cost_node = k\n",
    "            return lowest_cost_node\n",
    "\n",
    "        node = 0\n",
    "        while node != None:\n",
    "            cost = costs[node]\n",
    "            neighbors = friends[node]\n",
    "            for k in neighbors:\n",
    "                new_cost = cost + 1\n",
    "                if new_cost < costs[k]:\n",
    "                    costs[k] = new_cost\n",
    "            process.append(node)\n",
    "            node = find_lowest_cost_node()\n",
    "        tar_friends = [ i for i, j in enumerate(costs) if j == level]\n",
    "        tar_videos = [ video for friend in tar_friends for video in watchedVideos[friend]]\n",
    "        count = {}\n",
    "        for i in tar_videos:\n",
    "            count[i] = tar_videos.count(i)\n",
    "        count = dict(sorted(count.items(), key=lambda l:(l[1],l[0])))\n",
    "        return list(count.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        # 1. O(N^2) build adjacency list of undirected graph\n",
    "        n = len(watchedVideos)\n",
    "        g = friends \n",
    "        for i, friend in enumerate(friends):\n",
    "            for f in friend:\n",
    "                g[f].append(i)\n",
    "        \n",
    "        # 2. BFS start from vertex id, go `level` depth\n",
    "        videos = []\n",
    "        queue = deque([id])\n",
    "        visited = [False] * n \n",
    "        visited[id] = True \n",
    "        while queue and level:\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                for neighbor in g[node]:\n",
    "                    if not visited[neighbor]:\n",
    "                        queue.append(neighbor)\n",
    "                        visited[neighbor] = True \n",
    "\n",
    "                        if level == 1:\n",
    "                            videos += watchedVideos[neighbor]\n",
    "            level -= 1\n",
    "\n",
    "        # 3. order videos by frequency and name\n",
    "        freq = Counter(videos)\n",
    "        ans = sorted(freq.keys(), key=lambda x: (freq[x], x))\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], start: int, level: int) -> List[str]:\n",
    "        g = friends\n",
    "        q = [start]\n",
    "        k = 0\n",
    "        vis = set()\n",
    "        vis.add(start)\n",
    "        while q and k<level:\n",
    "            tmp = q[:]\n",
    "            q = []\n",
    "            k+=1\n",
    "            for x in tmp:\n",
    "                for y in g[x]: \n",
    "                    if y not in vis:\n",
    "                        vis.add(y)\n",
    "                        q.append(y)\n",
    "\n",
    "        rec = defaultdict(int)\n",
    "        for x in q:\n",
    "            for v in watchedVideos[x]:\n",
    "                rec[v] += 1\n",
    "        res = [[v,k] for k,v in rec.items()]\n",
    "        res.sort()\n",
    "        res = [k for v,k in res]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        # 1. O(N^2) build adjacency list of undirected graph\n",
    "        n = len(watchedVideos)\n",
    "        g = friends \n",
    "        for i, friend in enumerate(friends):\n",
    "            for f in friend:\n",
    "                g[f].append(i)\n",
    "        \n",
    "        # 2. BFS start from vertex id, go `level` depth\n",
    "        queue = deque([id])\n",
    "        visited = [False] * n \n",
    "        visited[id] = True \n",
    "        while queue and level:\n",
    "            nodes = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                for neighbor in g[node]:\n",
    "                    if not visited[neighbor]:\n",
    "                        queue.append(neighbor)\n",
    "                        nodes.append(neighbor)\n",
    "                        visited[neighbor] = True \n",
    "            level -= 1\n",
    "        \n",
    "        # 3. order video by frequency\n",
    "        videos = []\n",
    "        for node in nodes:\n",
    "            videos += watchedVideos[node]\n",
    "        \n",
    "        freq = Counter(videos)\n",
    "        ans = sorted(list(freq.keys()), key=lambda x: (freq[x], x))\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        max_val = float('inf')\n",
    "        n = len(friends)\n",
    "        costs = [max_val for _ in range(n)]\n",
    "        costs[id] = 0\n",
    "        process = []\n",
    "        def find_lowest_cost_node():\n",
    "            lowest_cost = max_val\n",
    "            lowest_cost_node = None\n",
    "            for k, v in enumerate(costs):\n",
    "                if k not in process and v < lowest_cost:\n",
    "                    lowest_cost = v\n",
    "                    lowest_cost_node = k\n",
    "            return lowest_cost_node\n",
    "\n",
    "        node = 0\n",
    "        while node != None:\n",
    "            cost = costs[node]\n",
    "            neighbors = friends[node]\n",
    "            for k in neighbors:\n",
    "                new_cost = cost + 1\n",
    "                if new_cost < costs[k]:\n",
    "                    costs[k] = new_cost\n",
    "            process.append(node)\n",
    "            node = find_lowest_cost_node()\n",
    "        tar_friends = [ i for i, j in enumerate(costs) if j == level]\n",
    "        tar_videos = [ video for friend in tar_friends for video in watchedVideos[friend]]\n",
    "        count = {}\n",
    "        for i in tar_videos:\n",
    "            count[i] = tar_videos.count(i)\n",
    "        count = dict(sorted(count.items(), key=lambda l:(l[1],l[0])))\n",
    "        return list(count.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        # 1. O(N^2) build adjacency list of undirected graph\n",
    "        n = len(watchedVideos)\n",
    "        g = friends \n",
    "        for i, friend in enumerate(friends):\n",
    "            for f in friend:\n",
    "                g[f].append(i)\n",
    "        \n",
    "        # 2. BFS start from vertex id, go `level` depth\n",
    "        videos = []\n",
    "        queue = deque([id])\n",
    "        visited = [False] * n \n",
    "        visited[id] = True \n",
    "\n",
    "        for _ in range(level):\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                for neighbor in g[node]:\n",
    "                    if not visited[neighbor]:\n",
    "                        queue.append(neighbor)\n",
    "                        visited[neighbor] = True \n",
    "\n",
    "        # 3. order videos by frequency and name\n",
    "        videos = [watchedVideos[i] for i in queue]\n",
    "        freq = Counter(itertools.chain(*videos))\n",
    "        ans = sorted(freq.keys(), key=lambda x: (freq[x], x))\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        max_val = float('inf')\n",
    "        n = len(friends)\n",
    "        costs = [max_val for _ in range(n)]\n",
    "        costs[id] = 0\n",
    "        process = []\n",
    "        def find_lowest_cost_node():\n",
    "            lowest_cost = max_val\n",
    "            lowest_cost_node = None\n",
    "            for k, v in enumerate(costs):\n",
    "                if k not in process and v < lowest_cost:\n",
    "                    lowest_cost = v\n",
    "                    lowest_cost_node = k\n",
    "            return lowest_cost_node\n",
    "\n",
    "        node = 0\n",
    "        while node != None:\n",
    "            cost = costs[node]\n",
    "            neighbors = friends[node]\n",
    "            for k in neighbors:\n",
    "                new_cost = cost + 1\n",
    "                if new_cost < costs[k]:\n",
    "                    costs[k] = new_cost\n",
    "            process.append(node)\n",
    "            node = find_lowest_cost_node()\n",
    "        tar_friends = [ i for i, j in enumerate(costs) if j == level]\n",
    "        tar_videos = [ video for friend in tar_friends for video in watchedVideos[friend]]\n",
    "        count = {}\n",
    "        for i in tar_videos:\n",
    "            count[i] = tar_videos.count(i)\n",
    "        count = dict(sorted(count.items(), key=lambda l:(l[1],l[0])))\n",
    "        return list(count.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        max_val = float('inf')\n",
    "        n = len(friends)\n",
    "        costs = [max_val for _ in range(n)]\n",
    "        costs[id] = 0\n",
    "        process = []\n",
    "        def find_lowest_cost_node():\n",
    "            lowest_cost = max_val\n",
    "            lowest_cost_node = None\n",
    "            for k, v in enumerate(costs):\n",
    "                if k not in process and v < lowest_cost:\n",
    "                    lowest_cost = v\n",
    "                    lowest_cost_node = k\n",
    "            return lowest_cost_node\n",
    "\n",
    "        node = 0\n",
    "        while node != None:\n",
    "            cost = costs[node]\n",
    "            neighbors = friends[node]\n",
    "            for k in neighbors:\n",
    "                new_cost = cost + 1\n",
    "                if new_cost < costs[k]:\n",
    "                    costs[k] = new_cost\n",
    "            process.append(node)\n",
    "            node = find_lowest_cost_node()\n",
    "        tar_friends = [ i for i, j in enumerate(costs) if j == level]\n",
    "        tar_videos = [ video for friend in tar_friends for video in watchedVideos[friend]]\n",
    "        count = {}\n",
    "        for i in tar_videos:\n",
    "            count[i] = tar_videos.count(i)\n",
    "        count = dict(sorted(count.items(), key=lambda l:(l[1],l[0])))\n",
    "        return list(count.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        max_val = float('inf')\n",
    "        n = len(friends)\n",
    "        costs = [max_val for _ in range(n)]\n",
    "        costs[id] = 0\n",
    "        process = []\n",
    "        def find_lowest_cost_node():\n",
    "            lowest_cost = max_val\n",
    "            lowest_cost_node = None\n",
    "            for k, v in enumerate(costs):\n",
    "                if k not in process and v < lowest_cost:\n",
    "                    lowest_cost = v\n",
    "                    lowest_cost_node = k\n",
    "            return lowest_cost_node\n",
    "\n",
    "        node = 0\n",
    "        while node != None:\n",
    "            cost = costs[node]\n",
    "            neighbors = friends[node]\n",
    "            for k in neighbors:\n",
    "                new_cost = cost + 1\n",
    "                if new_cost < costs[k]:\n",
    "                    costs[k] = new_cost\n",
    "            process.append(node)\n",
    "            node = find_lowest_cost_node()\n",
    "        tar_friends = [ i for i, j in enumerate(costs) if j == level]\n",
    "        tar_videos = [ video for friend in tar_friends for video in watchedVideos[friend]]\n",
    "        count = {}\n",
    "        for i in tar_videos:\n",
    "            count[i] = tar_videos.count(i)\n",
    "        count = dict(sorted(count.items(), key=lambda l:(l[1],l[0])))\n",
    "        return list(count.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(watchedVideos)\n",
    "        isSee = [0] * n\n",
    "        isSee[id] = 1\n",
    "        que = [id]\n",
    "        lv = 0\n",
    "        while que:\n",
    "            tmp = []\n",
    "            while que:\n",
    "                idx = que.pop(0)\n",
    "                for x in friends[idx]:\n",
    "                    if isSee[x] == 0:\n",
    "                        tmp.append(x)\n",
    "                        isSee[x] = 1\n",
    "            lv += 1\n",
    "            que = tmp\n",
    "            if lv == level:\n",
    "                break\n",
    "        count = Counter()\n",
    "        for idx in que:\n",
    "            for x in watchedVideos[idx]:\n",
    "                count[x] += 1\n",
    "        \n",
    "        xxx = sorted(count.items(), key=lambda kv: (kv[1], kv[0]), reverse=False)\n",
    "        ans = []\n",
    "        for x in xxx:\n",
    "            ans.append(x[0])\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        q=deque([id])\n",
    "        seen=set([id])\n",
    "        while level:\n",
    "            size=len(q)\n",
    "            for _ in range(size):\n",
    "                user=q.popleft()\n",
    "                for friend in friends[user]:\n",
    "                    if friend not in seen:\n",
    "                        q.append(friend)\n",
    "                        seen.add(friend)\n",
    "            level-=1\n",
    "        print(q)\n",
    "        c=Counter(reduce(lambda x,y:x+y,[watchedVideos[i] for i in q]))\n",
    "        print(c)\n",
    "        return sorted(c.keys(),key=lambda x:(c[x],x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "        #1）BFS：找出所有 Level k 的好友\n",
    "        q = deque([id])\n",
    "        used = [False] * n\n",
    "        \n",
    "        used[id] = True\n",
    "        for _ in range(level):#直到找到第k层好友\n",
    "            sx = len(q)\n",
    "            for i in range(sx):\n",
    "                u = q.popleft()\n",
    "                for nx in friends[u]:\n",
    "                    if not used[nx]:\n",
    "                        q.append(nx)\n",
    "                        used[nx] = True\n",
    "                        \n",
    "        #2）统计好友观看过的视频\n",
    "        freq = Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.pop()\n",
    "            for watched in watchedVideos[u]:\n",
    "                freq[watched] += 1\n",
    "                \n",
    "\t\t#3）将视频按照(频次,字节序)排序\n",
    "        videos = list(freq.items())\n",
    "        videos.sort(key=lambda x: (x[1], x[0]))\n",
    "\n",
    "        ans = [video[0] for video in videos]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        # 先找出对应level的好友\n",
    "        q = deque()\n",
    "        q.append(id)\n",
    "        seen = set()\n",
    "        seen.add(id)\n",
    "        for i in range(level):\n",
    "            l = len(q)\n",
    "            for _ in range(l):\n",
    "                u = q.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if v not in seen:\n",
    "                        q.append(v)\n",
    "                        seen.add(v)\n",
    "        rec = defaultdict(int)\n",
    "        for u in q:\n",
    "            for video in watchedVideos[u]:\n",
    "                rec[video] += 1\n",
    "        tmp = list(rec.items())\n",
    "        tmp.sort(key = lambda x:(x[1], x[0]))\n",
    "        res = [t[0] for t in tmp]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "\n",
    "        visited = [False] * n\n",
    "\n",
    "        q = collections.deque([id])\n",
    "        visited[id] = True\n",
    "\n",
    "        for _ in range(level):\n",
    "            span = len(q)\n",
    "            for i in range(span):\n",
    "                u = q.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if not visited[v]:\n",
    "                        q.append(v)\n",
    "                        visited[v] = True\n",
    "        \n",
    "        freq = collections.Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.pop()\n",
    "            for video in watchedVideos[u]:\n",
    "                freq[video] += 1\n",
    "        \n",
    "        videos = list(freq.items()) \n",
    "        videos.sort(key=lambda x: (x[1], x[0]))   \n",
    "        ans = [video[0] for video in videos]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "\n",
    "        visited = [False] * n\n",
    "\n",
    "        q = collections.deque([id])\n",
    "        visited[id] = True\n",
    "\n",
    "        for _ in range(level):\n",
    "            span = len(q)\n",
    "            for i in range(span):\n",
    "                u = q.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if not visited[v]:\n",
    "                        q.append(v)\n",
    "                        visited[v] = True\n",
    "        \n",
    "        freq = collections.Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.pop()\n",
    "            for video in watchedVideos[u]:\n",
    "                freq[video] += 1\n",
    "        \n",
    "        videos = list(freq.items()) \n",
    "        videos.sort(key=lambda x: (x[1], x[0]))   \n",
    "        ans = [video[0] for video in videos]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        cur_level = 0\n",
    "        friends_list = collections.deque([id])\n",
    "        seen = set([id])\n",
    "        while cur_level < level:\n",
    "            cur_level += 1\n",
    "            for _ in range(len(friends_list)):\n",
    "                f = friends_list.popleft()\n",
    "                for new_f in friends[f]:\n",
    "                    if new_f not in seen:\n",
    "                        friends_list.append(new_f)\n",
    "                        seen.add(new_f)\n",
    "        count = Counter()\n",
    "        for f in friends_list:\n",
    "            for ch in watchedVideos[f]:\n",
    "                count[ch] += 1\n",
    "        res = sorted(list(count.items()), key=lambda x: (x[1], x[0]))\n",
    "        return [i for i, _ in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "        \n",
    "        q = deque([id])\n",
    "        seen = [0]*n\n",
    "        seen[id] = 1\n",
    "        depth = 0\n",
    "        videos = Counter()\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if depth == level:\n",
    "                    videos.update(watchedVideos[node])\n",
    "                for neighbor in friends[node]:\n",
    "                    if not seen[neighbor]:\n",
    "                        seen[neighbor] = 1\n",
    "                        q.append(neighbor)\n",
    "            if depth == level:\n",
    "                videos = sorted(videos.items(),key=lambda x:(x[1],x[0]))\n",
    "                ans = [data[0] for data in videos]\n",
    "                return ans\n",
    "            depth += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "        D = [-1] * n \n",
    "        Q = deque([(0,id)])\n",
    "        D[id] = 0 \n",
    "        while Q:\n",
    "            d, u = Q.popleft() \n",
    "            for v in friends[u]:\n",
    "                if D[v] < 0:\n",
    "                    D[v] = d + 1\n",
    "                    Q.append((d+1, v)) \n",
    "        cnt = Counter() \n",
    "        #print(D)\n",
    "        for i in range(n):\n",
    "            if D[i] == level:\n",
    "                for x in watchedVideos[i]:\n",
    "                    cnt[x] += 1\n",
    "        arr = [(x, y) for x, y in cnt.items()]\n",
    "        arr.sort(key=lambda x : (x[1],x[0])) \n",
    "        return [x for x, y in arr]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        from collections import deque\n",
    "        q = deque([id])\n",
    "        s = set([id])\n",
    "        for i in range(level):\n",
    "            n = len(q)\n",
    "            j = 0\n",
    "            while j < n:\n",
    "                cur = q.popleft()\n",
    "                for index in friends[cur]:\n",
    "                    if index not in s:\n",
    "                        q.append(index)\n",
    "                        s.add(index)\n",
    "                j += 1\n",
    "        freq = collections.Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.pop()\n",
    "            for watched in watchedVideos[u]:\n",
    "                freq[watched] += 1\n",
    "        videos = list(freq.items())\n",
    "        videos.sort(key=lambda x: (x[1], x[0]))\n",
    "        ans = [video[0] for video in videos]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "        used = [False] * n\n",
    "        q = collections.deque([id])\n",
    "        used[id] = True\n",
    "        for _ in range(level):\n",
    "            span = len(q)\n",
    "            for i in range(span):\n",
    "                u = q.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if not used[v]:\n",
    "                        q.append(v)\n",
    "                        used[v] = True\n",
    "        \n",
    "        freq = collections.Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.pop()\n",
    "            for watched in watchedVideos[u]:\n",
    "                freq[watched] += 1\n",
    "\n",
    "        videos = list(freq.items())\n",
    "        videos.sort(key=lambda x: (x[1], x[0]))\n",
    "\n",
    "        ans = [video[0] for video in videos]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        q = [id]\n",
    "        d, vis = 0, set()\n",
    "        vis.add(id)\n",
    "        while q:\n",
    "            v = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                for y in friends[x]:\n",
    "                    if y not in vis:\n",
    "                        v += watchedVideos[y]\n",
    "                        vis.add(y) \n",
    "                        q.append(y)\n",
    "            if d + 1 == level:\n",
    "                break\n",
    "            d += 1\n",
    "\n",
    "        cnt = Counter(v)\n",
    "        st = sorted(cnt.items(), key=lambda x: (x[1], x[0]))\n",
    "        return [k for k, v in st]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "        used = [False] * n\n",
    "        q = collections.deque([id])\n",
    "        used[id] = True\n",
    "        for _ in range(level):\n",
    "            span = len(q)\n",
    "            for i in range(span):\n",
    "                u = q.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if not used[v]:\n",
    "                        q.append(v)\n",
    "                        used[v] = True\n",
    "        \n",
    "        freq = collections.Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.pop()\n",
    "            for watched in watchedVideos[u]:\n",
    "                freq[watched] += 1\n",
    "\n",
    "        videos = list(freq.items())\n",
    "        videos.sort(key=lambda x: (x[1], x[0]))\n",
    "\n",
    "        ans = [video[0] for video in videos]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "        people = deque([id])\n",
    "        used = [False]*n\n",
    "        used[id] = True\n",
    "        for _ in range(level):\n",
    "            span = len(people)\n",
    "            for i in range(span):\n",
    "                u = people.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if used[v] == False:\n",
    "                        people.append(v)\n",
    "                        used[v] = True\n",
    "        print(people)\n",
    "        count = Counter()\n",
    "        for num in people:\n",
    "            for video in watchedVideos[num]:\n",
    "                count[video] += 1\n",
    "        count = list(count.items())\n",
    "        print(count)\n",
    "        count.sort(key = lambda x: (x[1],x[0]))\n",
    "        print(count)\n",
    "        ans = [x[0] for x in count]\n",
    "        return ans\n",
    "        '''\n",
    "        n = len(friends)\n",
    "        used = [False] * n\n",
    "        q = collections.deque([id])\n",
    "        used[id] = True\n",
    "        for _ in range(level):\n",
    "            span = len(q)\n",
    "            for i in range(span):\n",
    "                u = q.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if not used[v]:\n",
    "                        q.append(v)\n",
    "                        used[v] = True\n",
    "        \n",
    "        freq = collections.Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.pop()\n",
    "            for watched in watchedVideos[u]:\n",
    "                freq[watched] += 1\n",
    "\n",
    "        videos = list(freq.items())\n",
    "        print(videos)\n",
    "        videos.sort(key=lambda x: (x[1], x[0]))\n",
    "        print(videos)\n",
    "        ans = [video[0] for video in videos]\n",
    "        return ans\n",
    "        '''\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(friends)\n",
    "        used = [False] * n\n",
    "        q = collections.deque([id])\n",
    "        used[id] = True\n",
    "        for _ in range(level):\n",
    "            span = len(q)\n",
    "            for _ in range(span):\n",
    "                u = q.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if not used[v]:\n",
    "                        q.append(v)\n",
    "                        used[v] = True\n",
    "        freq = collections.Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.pop()\n",
    "            for watched in watchedVideos[u]:\n",
    "                freq[watched] += 1\n",
    "        videos = list(freq.items())\n",
    "        videos.sort(key=lambda x: (x[1], x[0]))\n",
    "        ans = [video[0] for video in videos]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n = len(watchedVideos)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x,row in enumerate(friends):\n",
    "            for y in row:\n",
    "                g[x].append(y)\n",
    "\n",
    "        # 最短距离为k\n",
    "        ans  = []\n",
    "        queue = collections.deque()\n",
    "        queue.append(id)\n",
    "        visited = [0]*n\n",
    "        visited[id] = 1\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            newqueue = collections.deque()\n",
    "            for _ in range(size):\n",
    "                x = queue.popleft()\n",
    "                for y in g[x]:\n",
    "                    if not visited[y]:\n",
    "                        visited[y] = 1\n",
    "                        newqueue.append(y)\n",
    "            level -= 1\n",
    "            if level == 0:\n",
    "                break\n",
    "            queue = newqueue\n",
    "        print(newqueue)\n",
    "        if not newqueue:\n",
    "            return []\n",
    "        for i in newqueue:\n",
    "            ans.extend(watchedVideos[i])      \n",
    "        count = collections.Counter(ans)\n",
    "        res = [x[0] for x in sorted(count.items(),key=lambda x:(x[1],x[0]))]\n",
    "        return res\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        max_val = float('inf')\n",
    "        n = len(friends)\n",
    "        costs = [max_val for _ in range(n)]\n",
    "        costs[id] = 0\n",
    "        process = []\n",
    "        def find_lowest_cost_node():\n",
    "            lowest_cost = max_val\n",
    "            lowest_cost_node = None\n",
    "            for k, v in enumerate(costs):\n",
    "                if k not in process and v < lowest_cost:\n",
    "                    lowest_cost = v\n",
    "                    lowest_cost_node = k\n",
    "            return lowest_cost_node\n",
    "\n",
    "        node = 0\n",
    "        while node != None:\n",
    "            cost = costs[node]\n",
    "            neighbors = friends[node]\n",
    "            for k in neighbors:\n",
    "                new_cost = cost + 1\n",
    "                if new_cost < costs[k]:\n",
    "                    costs[k] = new_cost\n",
    "            process.append(node)\n",
    "            nodes = list(sorted([(k, v) for k, v in enumerate(costs) if k not in process],key=lambda l: l[1]))\n",
    "            if len(nodes) == 0:\n",
    "                break\n",
    "            node = nodes[0][0]\n",
    "        tar_friends = [ i for i, j in enumerate(costs) if j == level]\n",
    "        tar_videos = [ video for friend in tar_friends for video in watchedVideos[friend]]\n",
    "        count = {}\n",
    "        for i in tar_videos:\n",
    "            count[i] = tar_videos.count(i)\n",
    "        count = dict(sorted(count.items(), key=lambda l:(l[1],l[0])))\n",
    "        return list(count.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        n=len(watchedVideos)\n",
    "        find=[False]*n\n",
    "        find[id]=True\n",
    "        q=collections.deque()\n",
    "        q.append(id)\n",
    "        s=set()\n",
    "        for i in range(level):\n",
    "            #print(i)\n",
    "            m=len(q)\n",
    "            for j in range(m):\n",
    "                tp=q.popleft()\n",
    "                #if find[tp]:\n",
    "                #    continue\n",
    "                #find[tp]=True\n",
    "                for f in friends[tp]:\n",
    "                    if not find[f]:\n",
    "                        if i==level-1:\n",
    "                            s.add(f)\n",
    "                            find[f]=True\n",
    "                        else:\n",
    "                            q.append(f)\n",
    "                            find[f]=True\n",
    "        print(s)\n",
    "        c=collections.Counter()\n",
    "        for f in list(s):\n",
    "            for v in watchedVideos[f]:\n",
    "                c[v]+=1\n",
    "        print(c)\n",
    "        s=sorted(list(c.items()),key=lambda x:(x[1],x[0]))\n",
    "        ret=[]\n",
    "        for a,b in s:\n",
    "            ret.append(a)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        edges = defaultdict(set)\n",
    "        for i in range(len(friends)):\n",
    "            for friend in friends[i]:\n",
    "                edges[i].add(friend)\n",
    "        result = defaultdict(int)\n",
    "        visited = set([id])\n",
    "        dq = deque([id])\n",
    "\n",
    "        def bfs():\n",
    "            nonlocal result\n",
    "            depth = -1\n",
    "            while dq:\n",
    "                depth += 1\n",
    "                if depth == level:\n",
    "                    for num in dq:\n",
    "                        for video in watchedVideos[num]:\n",
    "                            result[video] += 1\n",
    "                    return\n",
    "                for _ in range(len(dq)):\n",
    "                    tmp = dq.popleft()\n",
    "                    reaches = edges[tmp]\n",
    "                    for reach in reaches:\n",
    "                        if reach in visited:\n",
    "                            continue\n",
    "                        dq.append(reach)\n",
    "                        visited.add(reach)\n",
    "\n",
    "        bfs()\n",
    "        result = list(result.items())\n",
    "        result.sort(key=lambda x: (x[1], x[0]))\n",
    "        return [it[0] for it in result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        '''\n",
    "        n = len(friends)\n",
    "        people = friends[id]\n",
    "        deep = level-1\n",
    "        used = [False]*n\n",
    "        used[id] = True\n",
    "        while deep:\n",
    "            tmp = []\n",
    "            for friend in people:\n",
    "                for num in friends[friend]:\n",
    "                    if used[num] == False:\n",
    "                        used[num] = True\n",
    "                        tmp.append(num)\n",
    "            people = tmp\n",
    "            deep -= 1\n",
    "        count = defaultdict(int)\n",
    "        for num in people:\n",
    "            if num == id:\n",
    "                continue\n",
    "            for video in watchedVideos[num]:\n",
    "                count[video] += 1\n",
    "        count = list(count.items())\n",
    "        print(count)\n",
    "        count.sort(key = lambda x: (x[1],x[0]))\n",
    "        print(count)\n",
    "        ans = [x[0] for x in count]\n",
    "        return ans\n",
    "        '''\n",
    "        n = len(friends)\n",
    "        used = [False] * n\n",
    "        q = collections.deque([id])\n",
    "        used[id] = True\n",
    "        for _ in range(level):\n",
    "            span = len(q)\n",
    "            for i in range(span):\n",
    "                u = q.popleft()\n",
    "                for v in friends[u]:\n",
    "                    if not used[v]:\n",
    "                        q.append(v)\n",
    "                        used[v] = True\n",
    "        \n",
    "        freq = collections.Counter()\n",
    "        for _ in range(len(q)):\n",
    "            u = q.pop()\n",
    "            for watched in watchedVideos[u]:\n",
    "                freq[watched] += 1\n",
    "\n",
    "        videos = list(freq.items())\n",
    "        print(videos)\n",
    "        videos.sort(key=lambda x: (x[1], x[0]))\n",
    "        print(videos)\n",
    "        ans = [video[0] for video in videos]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:\n",
    "        f = set([id])\n",
    "        seen = set()\n",
    "\n",
    "        while level > 0:\n",
    "            new_f = set()\n",
    "\n",
    "            for j in f:\n",
    "                for i in friends[j]:\n",
    "                    if i != id and i not in seen:\n",
    "                        new_f.add(i)\n",
    "                        seen.add(i)\n",
    "\n",
    "            f = new_f\n",
    "            level -= 1\n",
    "\n",
    "        record = {}\n",
    "\n",
    "        for i in f:\n",
    "            for m in watchedVideos[i]:\n",
    "                record.setdefault(m, 0)\n",
    "                record[m] += 1\n",
    "\n",
    "        return list(map(lambda x: x[0], sorted(record.items(), key = lambda x: f\"{x[1]:0100d}\" + x[0])))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
